package com.example.lettcode._202411._20241128;

/*
605. 种花问题
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

示例 1：
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2：
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false


示例3：
输入：flowerbed = [1,0,1,0,1,0,1], n = 1

提示：
1 <= flowerbed.length <= 2 * 104
flowerbed[i] 为 0 或 1
flowerbed 中不存在相邻的两朵花
0 <= n <= flowerbed.length
 */
public class _01_zhong_hua_wen_ti {

    public static void main(String[] args) {
        int[] flowerbed = {1, 1, 0, 0, 1};
        int n = 1;
        System.out.println(canPlaceFlowers(flowerbed, n));
    }


    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        int k = flowerbed.length;

        if (n == 0) {
            return true;
        }

        if (flowerbed.length == 1) {
            return flowerbed[0] == 0;
        }

        int m = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            int temp = flowerbed[i];
            if (temp == 1) {
                i++;
                continue;
            }
            if (i == 0) {
                if (flowerbed[i+1] == 0) {
                    flowerbed[i] = 1;
                    m++;
                }
            } else if (i == k - 1) {
                if (flowerbed[i - 1] == 0) {
                    flowerbed[i] = 1;
                    m++;
                }
            } else {
                if (flowerbed[i-1] == 0 && flowerbed[i+1] == 0) {
                    flowerbed[i] = 1;
                    m++;
                }
            }
            if (m == n) {
                return true;
            }
        }
        return n <= m;
    }


    public static boolean canPlaceFlowers2(int[] flowerbed, int n) {
        if (flowerbed == null || flowerbed.length == 0) {
            return n == 0;
        }

        int zeroFlower = 1;
        int canPlace = 0;

        for (int flower : flowerbed) {
            if (flower == 0) {
                zeroFlower++;
            } else {
                // 这一大片空地可以种的花
                canPlace += (zeroFlower - 1) / 2;

                if (canPlace >= n) {
                    return true;
                }

                zeroFlower = 0;
            }
        }

        zeroFlower++;
        canPlace += (zeroFlower - 1) / 2;
        return n <= canPlace;
    }

    public static boolean canPlaceFlowers3(int[] flowerbed, int n) {
        if(n <= 0){
            return true;
        }
        for(int i = 0; i < flowerbed.length; i ++){
            if(flowerbed[i] == 1){
                i ++;
            }else{
                /*
                    因为不可能存在两朵相邻的话，所以，此处两格两格的跳无问题
                    示例：
                        当存在两朵相邻的花时：1 1 0 0 1
                        当不存在两朵相邻的花时： 1 0 1 0 1,1后面肯定是0，所以当碰到1时，向后跳2位时，中间那位肯定是0
                        所以，当存在花时，向后跳两位
                        当下一位为土地时，中上花后，又可以跳两位

                        其余情况，跳一位就可以
                 */
                if(i + 1 == flowerbed.length || flowerbed[i + 1] == 0){
                    n --;
                    if(n <= 0){
                        return true;
                    }
                    i ++;
                }
            }
        }

        return false;
    }

}
